/*
 * @lc app=leetcode.cn id=400 lang=golang
 *
 * [400] 第 N 位数字
 */
package Solutions

import "strconv"

// @lc code=start

func findNthDigit(n int) int {
	var nine = []int{9, 90, 900, 9000, 90000, 900000, 9000000, 90000000, 900000000, 9000000000}
	var ten = []int{0, 0, 10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000, 1000000000}
	//二分

	if n < 10 {
		return n
	}
	left := 10
	right := n
	for {
		t := (left + right) / 2
		l := len(strconv.Itoa(t))
		pt := 0
		for i := 0; i < l-1; i++ {
			pt += (i + 1) * nine[i]
		}
		pt += (t - ten[l]) * l
		if pt == n {
			return (t - 1) % 10 //取最后一位
		}
		if pt > n {
			right = t
		} else {
			if pt+l >= n {
				pos := n - pt //取第pos位
				pos = l - pos + 1
				for j := 1; j < pos; j++ {
					t /= 10
				}
				return t % 10
			} else {
				left = t + 1
			}
		}
	}
}

// @lc code=end
